package com.leetcode.partition21;

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2022/2/10 18:54
 */
public class LC2097合法重新排列数对 {

    private static final int N = 100010, M = 100010;
    private static int[] head = new int[N], ver = new int[M], next = new int[M], din = new int[N], dout = new int[N];
    private static boolean[] st = new boolean[M];
    private static Map<Integer, Integer> map1 = new HashMap<>(N), map2 = new HashMap<>(N);

    private static int n = 0, m = 0, idx = 0, cnt = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int k = Integer.parseInt(reader.readLine());
        int[][] pairs = new int[k][2];
        for (int i = 0; i < k; i++) {
            String[] ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]);
            pairs[i] = new int[]{a, b};
        }
        int[][] answer = validArrangement(pairs);
        for (int i = 0; i < answer.length; i++) writer.write(Arrays.toString(answer[i]));
        writer.flush();
    }

    public static int[][] validArrangement(int[][] pairs) {
        Arrays.fill(head, -1);
        m = pairs.length;
        for (int[] pair : pairs) {
            int u = pair[0], v = pair[1];
            if (!map1.containsKey(u)) {
                map1.put(u, ++n);
                map2.put(n, u);
            }
            if (!map1.containsKey(v)) {
                map1.put(v, ++n);
                map2.put(n, v);
            }
            int a = map1.get(u), b = map1.get(v);
            add(a, b);
            din[b]++;
            dout[a]++;
        }
        int[][] answer = new int[m][2];
        //找起点
        int start = 1;
        for (int i = 1; i <= n; i++) {
            if (dout[i] == din[i] + 1) {
                start = i;
                break;
            }
        }
        //如果没有通过度找到起点就说明存在欧拉回路，任意起点都可
        dfs(start, answer);
        //反转一遍
        for (int i = 0; i < m / 2; i++) {
            int[] temp = answer[i];
            answer[i] = answer[m - i - 1];
            answer[m - i - 1] = temp;
        }
        return answer;
    }

    private static void dfs(int u, int[][] path) {
        int a = map2.get(u);
        for (int i = head[u]; i != -1; i = head[u]) {
            if (st[i]) {
                head[u] = next[i];
                continue;
            }
            st[i] = true;
            head[u] = next[i];
            dfs(ver[i], path);
            path[cnt++] = new int[]{a, map2.get(ver[i])};
        }
    }

    private static void add(int a, int b) {
        ver[idx] = b;
        next[idx] = head[a];
        head[a] = idx++;
    }
}
